class Solution:
	# @param {integer[]} height
	# @return {integer}
	def largestRectangleArea(self, height):
		ll = len(height)
		height.insert(0,0)
		height.append(0)
		left = [i for i in xrange(len(height))]
		right = [i+1 for i in xrange(len(height))]

		stk = []
		for i in xrange(1, ll+1):
			while len(stk) > 0 and height[stk[-1]] >= height[i]:
				stk.pop()
			if len(stk) == 0:
				left[i] = 1
			else:
				left[i] = stk[-1] + 1
			stk.append(i)

		stk = []
		for i in xrange(ll, 0, -1):
			while len(stk) > 0 and height[stk[-1]] >= height[i]:
				stk.pop()
			if len(stk) == 0:
				right[i] = ll+1
			else:
				right[i] = stk[-1]
			stk.append(i)

		ans = 0
		for i in xrange(len(height)):
			ans = max(ans, (right[i]-left[i])*height[i])
		return ans

if __name__ == '__main__':
	so = Solution()
	a = [2,4,3,6,4,1]
	print so.largestRectangleArea(a)